快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。
基本思想
1.在一列数组中取一个数作为基数
2.分区过程,先从右边开始小于这个基数的值放在左边,在从左边开始把大于基数的值放入右边
3.递归基数左边和右边区间重复第二部,直到只有一个值结束
图解
初始值
右边找小于基数的数值
- 挖坑,因为我们要交换位置所以要挖一个坑出来
把基数放入到坑中我们这里选6位基数,然后在右边找数填左边的坑。
右边开始找找到3比基数6小,交换它们的位置。
左边找大于基数的数值
- 左边开始找到了7大于基数的数字,交换位置后的值。
重复以上步骤,知道i和j相等的时候结束第一次排序
- 分区排序完后的值
1 | static void quick(int s[], int l, int r) { |
1 | public static void main(String[] args) { |